//
// Created by shenbin on 2022/5/12.
// https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
//

#ifndef ALGORITHM_TRAINNING_C05_LC105_H
#define ALGORITHM_TRAINNING_C05_LC105_H

#include <vector>

class LeetCode105 {
public:
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;

        TreeNode() : val(0), left(nullptr), right(nullptr) {}

        TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}

        TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {}
    };

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        this->preorder = preorder;
        this->inorder = inorder;
    }

private:
    vector<int> preorder;
    std::vector<int> inorder;

    /**
     * 递归构建/还原二叉数
     * 用preorder[l1..r1]和inorder[l2..r2]还原二叉树
     * @param l1：先序子树的根
     * @param r1：先序子树的右
     * @param l2：中序子树的左
     * @param r2：中序子树的右
     * @return
     */
    TreeNode *build(int l1, int r1, int l2, int r2) {
        if (l1 > r1) return nullptr;
        TreeNode *root = new TreeNode(preorder[l1]);
        int mid = l2; // l2是中序的左，要在中序中找根，如果找到，那么左子树就是：l2 -- mid-1
        while (inorder[mid] != root->val)mid++; //找到中序的根退出循环；
        // 中序：
        //  左子树：l2 -- mid-1
        //  根：mid
        //  右子树：mid+1 --r2
        root->left = build(l1 + 1, l1 + (mid - l2), l2, mid - 1);
        root->right = build(l1 + 1 + (mid - l2), r1, mid + 1, r2);
        return root;
    }
};

#endif //ALGORITHM_TRAINNING_C05_LC105_H
